最长回文子串

class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        if A[::-1] == A:
            return len(A)
        if len(A) == len(set(A)):
            return 1
        for k in range(len(A)-1,0,-1):
            for i in range(len(A)-k):
                if A[i:i+k][::-1] == A[i:i+k]:
                    return k

class Solution:
    def fun(self, s: str, begin: int, end: int) -> int:
        #每个中心点开始扩展
        while begin >= 0 and end < len(s) and s[begin] == s[end]: 
            begin -= 1
            end += 1
        #返回长度
        return end - begin - 1 
    def getLongestPalindrome(self , A: str) -> int:
        maxlen = 1
        #以每个点为中心
        for i in range(len(A) - 1): 
            #分奇数长度和偶数长度向两边扩展
            maxlen = max(maxlen, max(self.fun(A, i, i), self.fun(A, i, i + 1)))
        return maxlen

from collections import deque


class Solution:
    def getLongestPalindrome(self, A) -> int:
        # write code here
        for i in range(len(A) - 1, 0, -1):
            for j in range(len(A) - i):
                if self.palcheck(A[j:j+i+1]):
                    return i+1
        return 1

    def palcheck(self, A: str):
        char_dequeue = deque()
        for ch in A:
            char_dequeue.append(ch)
        check = True
        while len(char_dequeue)>1 and check:
            first = char_dequeue.popleft()
            last = char_dequeue.pop()
            if first!=last:
                check = False
        return check


a = Solution().getLongestPalindrome(input())
print(a)

manacher算法
时间复杂度：O(n) 空间复杂度：O(n)
参考文献：Manacher算法的详细讲解

class Solution:
    def manacher(self, s, n, dp):
        ms = ''
        ms += '$#'
        for i in range(n):
            ms += s[i]
            ms += '#'
        index = 0
        maxpos = 0
        for i in range(len(ms)):
            if i < maxpos:
                dp[i] = min(dp[2*index-i], maxpos-i)
            else:
                dp[i] = 1
            while i - dp[i] > 0 and i + dp[i] < len(ms) and ms[i-dp[i]] == ms[i+dp[i]]:
                dp[i] += 1
            if i + dp[i] > maxpos:
                maxpos = i + dp[i]
                index = i

    def getLongestPalindrome(self , A: str) -> int:
        n = len(A)
        dp = [0 for i in range(n*2 + 2)]
        self.manacher(A, n, dp)
        res = 0
        for i in range(n*2+2):
            res = max(res, dp[i]-1)
        return res

#动态规划
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        if not A:
            return 0
        dp = [[0 for i in range(len(A))] for j in range(len(A))]
        maxlen = 1
        for i in range(len(A)):
            for j in range(i,len(A)):
                if i == j:
                    dp[i][j] = 1
        for i in range(len(A)-2,-1,-1): # 这里左边指标用倒序是为了后面用到dp[i+1][j-1]时有值
            for j in range(1+i,len(A)):
                if A[i] == A[j]:
                    if j-i <= 2:
                        maxlen = max(maxlen, j-i+1)
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i+1][j-1]
                        if dp[i][j] == 1:
                            maxlen = max(maxlen, j-i+1)
        return maxlen

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def fun(self, s, left, right):
        while left >=0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1
    # Manacher算法, 感觉有点想剪枝的策略
    def Manacher(self, s):
        S = '#'.join(list(s))
        S = '@#' + S + '#'
        P = [0 for _ in range(len(S)+10)]
        idx, mx, max_num, max_id= 0,0,0,0

        for i in range(1, len(S)):
            # 如果当前的i在最大回文半径内，则进行选择当前最大半径下标到当前下标的距离  和  对称位置2*idx - 1的最大半径 最小值
            # 然后进行从对应的半径P[i]进行开始向左和右进行搜索
            P[i] = min(P[2 * idx - i], mx - i) if mx > i else 1
            while i - P[i] >=0 and i + P[i] < len(S) and S[i + P[i]] == S[i - P[i]]:
                P[i] += 1
            # 如果当前的最大半径index大于当前的mx，则进行替换
            # 更新最大回文半径中心id
            if i + P[i] > mx:
                mx = i + P[i]
                idx = i
            if P[i] > max_num:
                max_num = P[i]
                max_id = idx
        return max_num - 1            
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        # 最长回文子串 O(n^2)
        # 从左到右进行遍历字符串，然后计算1、中心字符扩散;2、两个字符扩散
#         rel = 1
#         for i in range(len(A) - 1):
#             rel = max(rel, max(self.fun(A, i, i), self.fun(A, i, i+1)))
        return self.Manacher(A)

TIPS:对于O(n^2)的做法：
1、通过将字符串进行反转，然后使用动态规划计算和原始字符串的最长共同子串；
2、通过中心扩散的做法， 遍历一遍字符串，对于每个字符进行向两边扩散计算回文子串的最大长度；

对于时间复杂度O(n)的做法：
Manacher算法：
1、首先将字符串‘123456’，处理成‘@#1#2#3#4#5#6#’的形式；
2、然后设定一个备忘录dp[i]，记录节点i的最大回文子串半径大小，设定额外两个变量idx，max_b,分别表示遍历过程中，当前字符前最大回文子串的中心下标以及最大回文子串的右界；
3、从头开始遍历，如果最大有界大于当前所遍历的字符下标，则取min(右界到当前下标的距离，当前下标在当下最大回文子串中心对称字符的最大半径P[2 *idx - cur_index]])，否则直接设定为1,
4、对当前字符可能的最大半径之后，进而从半径大小开始向两端遍历
5、如果更新后的当前字符的最大半径【右界】大于当前的右界，则进行更新右界和最大回文字符中心index
6、更新结果max_num【最终的max_num - 1则是最长回文子串的长度】

class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        dp = [[]]*len(A)
        dp[0] = [0]
        m = 1
        for i in range(1, len(A)):
            dp[i] = [i]
            for j in dp[i-1]:
                if j-1>=0 and A[j-1] == A[i]:
                    dp[i].append(j-1)
                    if i - j + 2 > m:
                        m = i - j + 2
                        print(i, j)
            if A[i] == A[i-1]:
                dp[i].append(i-1)
                if 2>m:
                    m=2
        return m
                

class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # f[i]: 以i为中心（奇数）或左中心（偶数）的最长回文长度
        # 膨胀法
        
        if len(A) == 1:
            return 1
        elif len(A) == 2:
            return 2 if A[0]==A[1] else 1
        
        f = [1 for _ in range(len(A))]
        
        for i in range(1, len(A)-1):
            # odd
            # 开始膨胀
            lpc = i-1
            rpc = i+1
            lengthOdd = 1
            while True:
                if lpc<0&nbs***bsp;rpc>=len(A)&nbs***bsp;A[lpc]!=A[rpc]:
                    break
                else:
                    lengthOdd += 2
                    lpc -= 1
                    rpc += 1
            # even
            lpc = i
            rpc = i+1
            lengthEven = 0
            # 开始膨胀
            while True:
                if lpc<0&nbs***bsp;rpc>=len(A)&nbs***bsp;A[lpc]!=A[rpc]:
                    break
                else:
                    lengthEven += 2
                    lpc -= 1
                    rpc += 1
            f[i] = max(lengthOdd, lengthEven)
        return max(f)

class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        arr = []
        for i in range(len(A)):
            for j in range(i,len(A)):
                if A[i] == A[j] and A[i+1:j] == A[i+1:j][::-1]:
                    arr.append(j-i+1)
        return max(arr)

class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        n=len(A)
        dp=[[False]*n for _ in range(n)]
        max_len=1
        for i in range(n):
            dp[i][i]=True
        for L in range(2,n+1):
            for i in range(n):
                j=L+i-1
                if j>=n:
                    break
                if A[i]!=A[j]:
                    dp[i][j]=False
                else:
                    if L<=3:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
                if dp[i][j]==True and L>max_len:
                    max_len=L
        return max_len
       

class Solution:
    def getLongestPalindrome(self , A: str, n: int) -> int:
        # write code here
        A = list(A)
        results = []
        for idx, item in enumerate(A):
            
            # 检测 奇数个
            tmp = [item]
            for i in range(1, 1+min(idx, len(A)-idx-1)):
                if A[idx-i] == A[idx+i]:
                    tmp = [A[idx-i]] + tmp + [A[idx+i]]
                else:
                    break
            if len(tmp) >= len(results):
                results = tmp
            
            # 检测 偶数个
            tmp = []
            for i in range(1, 1+min(idx+1, len(A)-idx-1)):
                if A[idx-i+1] == A[idx+i]:
                    tmp = [A[idx-i+1]] + tmp + [A[idx+i]]
                else:
                    break
            if len(tmp) >= len(results):
                results = tmp
            
        return len(results)